#include <string>
#include <unordered_map>
#include <vector>

template<class Index = char, class T = std::string>
class subsqequence_statistics
{
public:

	static size_t subsequence_statistics(const T& source, const T& sub)
	{
		size_t sourceSize = source.size();
		size_t subSize = sub.size();
		if (subSize > sourceSize)
		{
			return 0;
		}

		std::vector<size_t> dp(subSize + 1, 0);
		dp[0] = 1;

		for (size_t row = 1; row <= sourceSize; ++row)
		{
			for (size_t col = subSize; col >= 1; --col)
			{
				if (source[row - 1] == sub[col - 1])
				{
					dp[col] = dp[col] + dp[col - 1];
				}
			}
		}

		return dp[subSize];
	}

	static size_t multi_subsequence_statistics(const T& source, const T& sub)
	{
		size_t sourceSize = source.size();
		size_t subSize = sub.size();
		if (subSize > sourceSize)
		{
			return 0;
		}

		std::vector<size_t> dp(subSize + 1, 0);
		dp[0] = 1;

		std::unordered_map<Index, std::vector<size_t>> hash;
		for (size_t i = 0; i < subSize; ++i)
		{
			hash[sub[i]].push_back(i);
		}

		for (size_t i = 0; i < sourceSize; ++i)
		{
			if (!hash.count(source[i]))
			{
				continue;
			}

			std::vector<size_t>& index = hash[source[i]];
			for (int back = index.size() - 1; back >= 0; --back)
			{
				dp[index[back] + 1] = dp[index[back] + 1] + dp[index[back]];
			}
		}

		return dp[subSize];
	}
};